package 左哥算法.ch20树状数组;

import java.util.Arrays;
import java.util.Random;

/**
 * 给你一个数组。
 * 对数组有n次修改。
 * 要求修改后返回数组中的最小值
 */
public class 树状数组求区间最大最小值 {

    public static void main(String[] args) {
        long[] arr = {3, 10, 10};
        TreeArray treeArray = new TreeArray(arr);
        treeArray.update(1,4);
        System.out.println(treeArray.query(3));
    }
    static {
        compare();
    }

    public static void compare() {
        int count = 100000;
        Random r = new Random();
        while (count-- > 0) {
            int n = r.nextInt(10) + 1;
            long[] arr = new long[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = r.nextInt(100);
            }
            TreeArray treeArray = new TreeArray(arr);
            Answer answer = new Answer(arr);

            int c = r.nextInt(10) + 1;    //操作次数
            StringBuilder builder = new StringBuilder();
            while (c-- > 0) {
                int op = r.nextInt(2);
                int i = r.nextInt(n) + 1;
                switch (op) {
                    case 0:
                        long val = r.nextInt(10);
                        builder.append(i).append(";update:").append(val).append("\n");
                        treeArray.update(i, val);
                        answer.update(i, val);
                        break;
                    case 1:
                        long solution = treeArray.query(i);
                        long ans = answer.query(i);
                        if (ans != solution) {
                            System.out.println("---------------");
                            System.out.println(Arrays.toString(arr));
                            System.out.println(builder);
                            System.out.println("query:" + i);
                            System.out.println("ans:" + ans + "\tsolution:" + solution);
                        }
                        break;
                }
            }
        }
    }

    static class TreeArray {
        long[] tree; // 树状数组，用于存储区间最小值
        long[] origins; // 原数组，用于存储原始数据

        // 构造函数，接收一个整型数组作为参数，用于初始化树状数组
        public TreeArray(long[] origin) {
            this.tree = new long[origin.length + 1]; // 初始化树状数组，下标从1开始
            this.origins = new long[origin.length + 1]; // 初始化原数组，下标从1开始
            Arrays.fill(tree, Long.MAX_VALUE); // 将树状数组的所有元素初始化为最大值
            for (int i = 0; i < origin.length; i++) { // 遍历原数组，更新树状数组
                update(i + 1, origin[i]); // 更新树状数组
            }
        }

        // 查询0-n位置的最小值
        public long query(int n) {
            long min = Long.MAX_VALUE; // 初始化最小值为最大值
            while (n > 0) { // 当n大于0时，继续查询
                min = Math.min(min, tree[n]); // 更新最小值
                n -= lowbit(n); // 更新n的值
            }
            return min; // 返回最小值
        }

//        public long query(int L,int R){
//            return query(R)-query(L-1);
//        }

        // 更新位置n的值为val，只有当新值小于原来的最小值时才进行更新
        public void update(int n, long val) {
            this.origins[n] = val; // 更新原数组的值
            int i;
            while (n < tree.length) {   //logn
                tree[n] = origins[n];
                i = lowbit(n);
                //logN
                for (int j = 1; j < i; j <<= 1) {   //更新管辖区间的最小值。可以用j++代替j<<=1
                    tree[n] = Math.min(tree[n], tree[n - j]);
                }
//                tree[n]=Math.min(tree[n],query(n-1));
                n += i;
            }
        }

        // 取x的最后一位1，这是树状数组的基础操作，用于确定树状数组中元素的父子关系
        public int lowbit(int x) {
            return x & -x; // 返回x的最后一位1
        }
    }

    static class Answer {
        long[] arr;

        public Answer(long[] arr) {
            this.arr = new long[arr.length + 1];
            System.arraycopy(arr, 0, this.arr, 1, arr.length);
        }

        public void update(int i, long val) {
            this.arr[i] = val;
        }

        public long query(int L, int R) {
            long min = Long.MAX_VALUE;
            while (L <= R) {
                min = Math.min(min, arr[L++]);
            }
            return min;
        }

        public long query(int n) {
            long min = Long.MAX_VALUE;
            for (int i = 1; i <= n; i++) {
                min = Math.min(min, arr[i]);
            }
            return min;
        }
    }
}
